package 力扣.并查集.最小生成树;

import java.util.Arrays;
import java.util.Comparator;

public class Kruskal {
    public static void main(String[] args) {

    }
    /**
     * @param n 点数
     * @param m 边数
     * @param conn 权重
     * @return
     */
     private long kruskal(int n , int m ,int[][] conn){
         init(n);//帮派的初始化
         Arrays.sort(conn,0,m,new Comparator<int[]>(){//对权值进行从小到大的排序
             public int compare(int[] o1,int [] o2){
                 return o1[2] - o2[2];
             }
         });
         for (int i = 0; i < m; i++) {//所有帮派合并为一个帮派
             Union(conn[i][0],conn[i][1],conn[i][2]);
         }
         return cost;
     }
     private int[] F;
     private Long cost;
    private void init(int n) {
         F = new int[n];
        for (int i = 0; i < n; i++) {
            F[i] = i;
        }
        cost = 0L;
    }
    private int Find(int x){
        if (x == F[x]){
            return x;
        }
        return F[x] = Find(F[x]);
    }
    private void  Union(int x,int y,int pay){
        if (Find(x) != Find(y)){//大哥不同，这说明这是两个帮派，则需要进行合并
            cost += pay;
        }
        F[Find(x)] = Find(y);
    }
}
